package clustering_algorithms;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
import java.util.Vector;

public class k_means {
	
	
	
	protected ArrayList<HashMap<Integer, Float>> m_vectors_to_cluster;
	protected int m_number_of_clusters;
	float m_maximal_centroid_movement = 0;
	public float m_sum_of_distnce = Float.MAX_VALUE;
	float[][] m_distances_from_centroid; 
	List<Boolean> m_changed_centroid = new ArrayList<Boolean>();
	
	public k_means(ArrayList<HashMap<Integer, Float>> vectors_to_cluster, int number_of_clusters, float maximal_centroid_movement) throws IOException
	{
		ArrayList<HashMap<Integer, Float>> temp = new ArrayList<HashMap<Integer,Float>>();
		
		m_number_of_clusters = number_of_clusters;
		m_vectors_to_cluster = vectors_to_cluster;
		
		
		
		
		
		m_maximal_centroid_movement = maximal_centroid_movement;		
		m_distances_from_centroid = new float[m_vectors_to_cluster.size()][number_of_clusters]; 

	}

	ArrayList<HashMap<Integer, Float>> m_centroids = new ArrayList<HashMap<Integer, Float>>();
	@SuppressWarnings("unchecked")
	public HashMap<Integer, HashSet<Integer>> DoTheClustering()
	{
		ArrayList<Integer> centroids_idx = ChooseSeeds();
		
		for (int i =0; i< centroids_idx.size();++i)
		{
			m_centroids.add((HashMap<Integer, Float>) m_vectors_to_cluster.get(centroids_idx.get(i)).clone());
			m_changed_centroid.add(true);
		}
		
		ArrayList<HashMap<Integer, Float>>  centroids_prev = new ArrayList<HashMap<Integer, Float>>();
		//init the centroid
		
		int number_of_iteration = 0;

		FindClosestToCentroid();
 
		float previous_sum_of_distnce = Float.MAX_VALUE;
		//iterate until there is no more change

		Set<Integer> clusters_id = new HashSet<Integer>();
		for(int i =0; i< m_number_of_clusters;++i)
		{
			clusters_id.add(i);
		}
		while(previous_sum_of_distnce - m_sum_of_distnce > 0)
		{
			previous_sum_of_distnce = m_sum_of_distnce;
			float min_tf_idf = Float.MAX_VALUE;
			centroids_prev.clear();
			//all_centroid_movement_in_last_iteration = 0;
			
			centroids_prev = m_centroids;
			m_centroids = new ArrayList<HashMap<Integer,Float>>();
			for(int cluster_id  :  clusters_id)
			{	
				m_centroids.add(new HashMap<Integer, Float>());
				int number_of_docs_in_cluster = m_clustered_docs.get(cluster_id).size();
				HashMap<Integer, Float> current_cluster = m_centroids.get(cluster_id);
				
				for(int doc_i : m_clustered_docs.get(cluster_id) )
				{
					HashMap<Integer, Float> current_doc = m_vectors_to_cluster.get(doc_i); 
					if(doc_i%1000 == 0)
					{
						System.out.println("doc_i" + ((Integer)doc_i).toString());	
					}					
					
					//create the centroid
					for(int term_id : current_doc.keySet())
					{
						
						Float current_doc_term_weight = current_doc.get(term_id);
						if(min_tf_idf > current_doc_term_weight)
						{
							min_tf_idf = current_doc_term_weight;
						}
						Float cnteroid_term_weight = current_cluster.get(term_id);
						Float current_centroid_term_weight = (cnteroid_term_weight == null) ? 0f : cnteroid_term_weight;
						current_centroid_term_weight += current_doc_term_weight;///number_of_docs_in_cluster;
						current_cluster.put(term_id, current_centroid_term_weight);
					}
				}				
				
				System.out.println("start");
				Iterator<Integer> term_it = current_cluster.keySet().iterator();
				while (term_it.hasNext()) 
				{
					Integer term_id = term_it.next().intValue(); 
					
					Float cnteroid_term_weight = current_cluster.get(term_id);
					Float current_centroid_term_weight = (cnteroid_term_weight == null) ? 0f : cnteroid_term_weight;
					
					current_centroid_term_weight /= (float)number_of_docs_in_cluster;
					current_cluster.put(term_id, current_centroid_term_weight);
					
					
					if(current_centroid_term_weight < 0.000000001)
					{
						term_it.remove();
					}
					
					//current_centroid_term_weight = current_cluster.getOrDefault(term_id, 0f);
				}
				System.out.println("end");
				
			}
			
			//check for chnage in the 
			m_changed_centroid.clear();
			for(int cluster_i =0; cluster_i < m_centroids.size(); ++cluster_i)
			{
				float distance_from_previous_centroid = CalcEuclidianDistance(m_centroids.get(cluster_i), centroids_prev.get(cluster_i));
				m_changed_centroid.add(distance_from_previous_centroid != 0f);			
			}
			
			
			FindClosestToCentroid();
			System.out.println("number_of_iteration: "+((Integer)number_of_iteration).toString());
			number_of_iteration++;
			System.out.println(" m_sum_of_distnce: " + ((Float)m_sum_of_distnce).toString());

		}
		return m_clustered_docs;		
	}
	
	
	HashMap<Integer, HashSet<Integer>> m_clustered_docs = new HashMap<Integer, HashSet<Integer>>();
	
	
	private float get_distance_from_centroid(int doc_i, HashMap<Integer, Float> examined_vector, int centroid_represent)
	{
		float distance = 0;
		if(m_changed_centroid.get(centroid_represent))
		{
			HashMap<Integer, Float> centroid_vector = m_centroids.get(centroid_represent);
			centroid_vector = m_centroids.get(centroid_represent);
			//System.out.println("tic2 "+ (System.currentTimeMillis()- start));
			distance = CalcEuclidianDistance(examined_vector, centroid_vector);
			//m_distances_from_centroid[doc_i][centroid_represent] = distance;
		}
		else
		{
			distance = m_distances_from_centroid[doc_i][centroid_represent];
		}
		return distance; 
	}
	 
	private void  FindClosestToCentroid()
	{
		m_clustered_docs = new HashMap<Integer, HashSet<Integer>>();
		//HashMap<Integer, HashSet<Integer>> clustered_docs = new HashMap<Integer, HashSet<Integer>>();
		
		
		Float sum_of_distance = 0f;

		
		long start = 0;
		start = System.currentTimeMillis();
	
		
		for(int doc_i =0; doc_i< m_vectors_to_cluster.size() ; ++doc_i)
		{
			int best_cluse_index = 0;
			HashMap<Integer, Float> examined_vector = m_vectors_to_cluster.get(doc_i);
			float min_distance = get_distance_from_centroid(doc_i, examined_vector, 0);

			m_distances_from_centroid[doc_i][0] = min_distance;
			for(int centroid_represent = 1; centroid_represent < m_centroids.size(); ++centroid_represent)
			{
				float distance = get_distance_from_centroid(doc_i, examined_vector, centroid_represent);
				m_distances_from_centroid[doc_i][centroid_represent] = distance;
				
				if(distance < min_distance)
				{
					min_distance = distance;
					best_cluse_index = centroid_represent;
				}					
			}
			if(doc_i %1000 == 0)
			{
				System.out.println("tic "+ (System.currentTimeMillis()- start));	
			}
			if(!m_clustered_docs.containsKey(best_cluse_index))
			{
				 
				
				m_clustered_docs.put(best_cluse_index, new HashSet<Integer>());
			}
			sum_of_distance += min_distance;
			//System.out.println("tic4 "+ (System.currentTimeMillis()- start));
			m_clustered_docs.get(best_cluse_index).add(doc_i);
			
			m_sum_of_distnce = sum_of_distance; 
			
 		}
		//if(doc_i %1000 == 0)
		{
			System.out.println("tic "+ (System.currentTimeMillis()- start));	
		}
		
		
	}
	
	
	protected ArrayList<Integer> ChooseSeeds()
	{
		Set<Integer> seeds =  pickRandom(m_number_of_clusters, m_vectors_to_cluster.size());
		ArrayList<Integer> return_value = new ArrayList<Integer>();
		return_value.addAll(seeds);		
		/*
		for(int i=0; i <m_number_of_clusters; ++i)
		{
			return_value.add(i);	
		}
		
		*/
		
		return return_value;		
	}
	
	
	private Set<Integer> pickRandom(int n, int k) {
	    Random random = new Random(); // if this method is used often, perhaps define random at class level
	    random.setSeed(0);
	    Set<Integer> picked = new HashSet<Integer>();
	    while(picked.size() < n) {
	        picked.add(random.nextInt(k));
	    }
	    return picked;
	}
	
	//private float CalcEuclidianDistance(Float[][] all_vectors, int doc_i_a, int doc_i_b)
	
	protected float CalcEuclidianDistance(HashMap<Integer, Float> vec_a, HashMap<Integer, Float> vec_b)
	{
		float sum_of_square = 0;
		//find the smallest from the two vectors in order to save iterations
		HashMap<Integer, Float> iterate_master_vector = null, iterate_slave_vector = null;
		if(vec_a.size() > vec_b.size())
		{
			iterate_master_vector = vec_a;
			iterate_slave_vector = vec_b;
		}
		else
		{
			iterate_master_vector = vec_b;
			iterate_slave_vector = vec_a;
		}
		
		HashSet<Integer> all_terms = new HashSet<Integer>();
		all_terms.addAll(iterate_master_vector.keySet());
		all_terms.addAll(iterate_slave_vector.keySet());
		
		
		all_terms.addAll(iterate_slave_vector.keySet());
		//iterate_master_vector.keySet().addAll(arg0)
		for(Integer term_id :all_terms )
		{
			//if(!iterate_slave_vector.containsKey(term_id))
			Float temp = iterate_master_vector.get(term_id);
			float master_tf_idf = (temp == null) ? 0f : temp;
			temp = iterate_slave_vector.get(term_id);
			float slave_tf_idf = (temp == null) ? 0f : temp;
			sum_of_square += Math.pow(master_tf_idf - slave_tf_idf, 2);		
		}
		
		//float reutrn_value = (float) Math.sqrt(sum_of_square); 
		float reutrn_value = (float) sum_of_square;
		
		return reutrn_value;
	}
	
	private float[] extract_vector_from_matrix(float[][] matrix, int col_i)
	{
		float[] return_value = new float[matrix.length];
		for(int t_i = 0; t_i < matrix.length; ++t_i)
		{
			return_value[t_i] = matrix[t_i][col_i];
		}
		return return_value;
	}
	
}
